In this chapter we go over the formal definitions and proofs related to the deterministic finite automata (DFA) computational model. Our main goal is to use the DFA model as a warm-up towards the more general Turing machine model. That being said, the DFA model is interesting in its own right. Below you can find some of the applications of deterministic finite automata:
Anything that processes information can be called a computer. However, there can be restrictions on how the information can be processed (either universal restrictions imposed by, say, the laws of physics, or restrictions imposed by the particular setting we are interested in).
A computational model is a set of allowed rules for information processing. Given a computational model, we can talk about the computers (or machines) allowed by the computational model. A computer is a specific instantiation of the computational model, or in other words, it is a specific collection of information processing rules allowed by the computational model.
Note that even though the terms “computer” and “machine” suggest a physical device, in this course we are not interested in physical representations that realize computers, but rather in the mathematical representations. The term algorithm is synonymous to computer (and machine) and makes it more clear that we are not necessarily talking about a physical device.
In this section we give the basic definitions regarding the computational model known as deterministic finite automata.
A deterministic finite automaton (DFA) is a -tuple where
is a non-empty finite set (which we refer to as the set of states of the DFA);
is a non-empty finite set (which we refer to as the alphabet of the DFA);
is a function of the form (which we refer to as the transition function of the DFA);
is an element of (which we refer to as the start state of the DFA);
is a subset of (which we refer to as the set of accepting states of the DFA).
It is very common to represent a DFA with a state diagram. Below is an example of how we draw a state diagram of a DFA:
In this example, , , . The labeled arrows between the states encode the transition function , which can also be represented with a table as shown below (row and column contains ).
The start state is labeled with , but if another label is used, we can identify the start state in the state diagram by identifying the state with an arrow that does not originate from another state and goes into that state.
In the definition above, we used the labels . One can of course use other labels when defining a DFA as long as it is clear what each label represents.
We’ll consider two DFAs to be equivalent/same if they are the same machine up to renaming the elements of the sets and . For instance, the two DFAs below are considered to be the same even though they have different labels on the states and use different alphabets.
The flexibility with the choice of labels allows us to be more descriptive when we define a DFA. For instance, we can give labels to the states that communicate the “purpose” or “role” of each state.
Let be a DFA and let be a string over an alphabet (so for each ). The computation path of with respect to is a specific sequence of states (where each ). We’ll often write this sequence as follows.
These states correspond to the states reached when the DFA reads the input one character at a time. This means , and An accepting computation path is such that , and a rejecting computation path is such that .
We say that accepts a string (or “ accepts”, or “”) if the computation path of with respect to is an accepting computation path. Otherwise, we say that rejects the string (or “ rejects”, or “”).
Let be the DFA in Note (State diagram of a DFA). For ease of reference, we present the state diagram once again here.
For input string , the computation path of with respect to is
Since is not in , this is a rejecting computation path, and therefore rejects , i.e. .
Let be a DFA. The transition function extends to , where is defined as the state we end up in if we start at and read the string . Or in other words, The star in the notation can be dropped and can be overloaded to represent both a function and a function . Using this notation, a word is accepted by the DFA if .
Let be a decision problem and let be a DFA over the same alphabet. We say that solves (or decides, or computes) if the input/output behavior of matches exactly, in the following sense: for all , .
If is the language corresponding to , the above definition is equivalent to saying that solves (or decides, or computes) if the following holds:
if , then accepts (i.e. );
if , then rejects (i.e. ).
The following DFA solves the language consisting of all binary strings that contain an even number of ’s.
The following DFA solves the language consisting of all binary strings that end with .
.
.
Below, all missing transitions go to a rejecting sink state (so the DFA actually has 6 states in total).
Take the DFA above and flip the accepting and rejecting states.
Below, all missing transitions go to a rejecting sink state.
Let be a finite language, i.e., it contains a finite number of words. At a high level, describe why there is a DFA solving .
It is a good idea to first think about whether languages of size are regular. Are languages of size regular? When you draw DFAs for such languages, the basic idea is to “hard-code” the words in the language into the state-diagram of the DFA (this is what we did for part 1 of Exercise (Draw DFAs)). So for each word in the language, there would be a path in the DFA corresponding to that word that ends in an accepting state. This idea works whenever the language in consideration has a finite number of words. The number of states in the DFA will depend on the number of words in the language and the length of those words, but since the language is finite (and each word has finite-length), all the words in the language can be hard-coded using a finite number of states.
A language is called a regular language if there is a deterministic finite automaton that solves .
All the languages in Exercise (Draw DFAs) are regular languages.
The language is regular. Go through some examples to see if you can notice a pattern and come up with an alternate description for the language.
The answer is yes because the language is pretty much the same as the language in Exercise (Draw DFAs), part 3 (except that the starting state should also be accepting).
We denote by the set of all regular languages (over the default alphabet ).
Our goal is to show that is not regular. The proof is by contradiction. So let’s assume that is regular.
Since is regular, by definition, there is some deterministic finite automaton that solves . Let denote the number of states of . Consider the following set of strings: . Each string in , when fed as input to , ends up in one of the states of . By the pigeonhole principle (thinking of the strings as pigeons and the states as holes), we know that there must be two strings in that end up in the same state. In other words, there are , with , such that the string and the string end up in the same state. This implies that for any string , and end up in the same state. We’ll now reach a contradiction, and conclude the proof, by considering a particular such that and end up in different states.
Consider the string . Then since solves , we know must end up in an accepting state. On the other hand, since , is not in the language, and therefore cannot end up in an accepting state. This is the desired contradiction.
In the proof of the above theorem, we defined the set and then applied the pigeonhole principle. Explain why picking the following sets would not have worked in that proof.
With we can still apply the pigeonhole principle to conclude that there are two strings and , , that must end up in the same state. However, to reach a contradiction, we need to find a string such that exactly one of and is in the language, and the other is not. On the other hand, any string starting with a is not in the language.
The argument is the same as above, with the key observation being the following. When we apply the pigeonhole principle to conclude that two strings in must end up in the same state, we have no control over which two strings in end up in the same state. Therefore, our argument must work no matter which two strings in end up in the same state. For the given to us, the two strings that end up in the same state could be and , and so we would run into the same problem as in the previous part.
Our goal is to show that is not regular. The proof is by contradiction. So let’s assume that is regular.
Since is regular, by definition, there is some deterministic finite automaton that solves . Let denote the number of states of . For , let denote the state that reaches after reading . By the pigeonhole principle, we know that there must be a repeat among . In other words, there are with such that . This means that the string and the string end up in the same state in Therefore, and , for any string , end up in the same state in . We’ll now reach a contradiction, and conclude the proof, by considering a particular such that and end up in different states.
Consider the string . Then since solves , we know must end up in an accepting state. On the other hand, since , is not in the language, and therefore cannot end up in an accepting state. This is the desired contradiction.
In Exercise (Would any set of pigeons work?) we saw that the “pigeon set” that we use to apply the pigeonhole principle must be chosen carefully. We’ll call a pigeon set a fooling pigeon set if it is a pigeon set that “works”. That is, given a DFA with states that is assumed to solve a non-regular , a fooling pigeon set of size allows us to carry out the contradiction proof, and conclude that is non-regular. Identify the property that a fooling pigeon set should have.
A fooling pigeon set is such that for all , there exists a such that exactly one of and is in , and the other is not. (Note that the choice of for different pairs and may be different.)
The crux of a non-regularity proof is to show that for any (which denotes the number of states of a DFA that is assumed to solve ), there is a fooling pigeon set of size at least . Since is arbitrary, showing that a language is non-regular really amounts to finding an infinite-size fooling pigeon set. In the case of the language , the infinite-size fooling pigeon set is .
Our goal is to show that is not regular. The proof is by contradiction. So let’s assume that is regular.
Since is regular, by definition, there is some deterministic finite automaton that solves . Let denote the number of states of . For , let denote the state that reaches after reading (i.e. ). By the pigeonhole principle, we know that there must be a repeat among (a sequence of states). In other words, there are indices with such that . This means that the string and the string end up in the same state in . Therefore, and , for any string , end up in the same state in . We’ll now reach a contradiction, and conclude the proof, by considering a particular such that ends up in an accepting state but ends up in a rejecting state (i.e. they end up in different states).
Consider the string . Then , and therefore must end up in an accepting state. On the other hand, . We claim that this word must end up in a rejecting state because cannot be written as a power of (i.e., cannot be written as for some ). To see this, note that since , we have which implies that if , then (which is impossible). So cannot be written as for , and therefore leads to a reject state in as claimed.
In the next exercise, we’ll write the proof in a slightly different way to offer a slightly different perspective. In particular, we’ll phrase the proof such that the goal is to show no DFA solving can have a finite number of states. This is done by identifying an infinite set of strings that all must end up in a different state (this is the fooling pigeon set that we defined in Exercise (A fooling pigeon set)). Once you have a set of strings such that every string in must end up in a different state, we can conclude any DFA solving the language must have at least states.
This slight change in phrasing of the non-regularity proof makes it clear that even if is regular, the technique can be used to prove a lower bound on the number of states of any DFA solving .
Our goal is to show that is not regular. Consider the set of strings . We claim that in any DFA solving , no two strings in can end up in the same state. To prove this claim, let’s go by contradiction, and assume that there are two strings in , and , , that end up in the same state. Then for any , the strings and must end up in the same state. But for , must end up in an accepting state, whereas must end up in a rejecting state. This is a contradiction.
Since we have identified an infinite set of strings that all must end up in a different state, we conclude that there cannot be a DFA solving , since by definition, DFAs have a finite number of states.
In this section we will be interested in the following question. Given regular languages, what operations can we apply to them (e.g. union, intersection, concatenation, etc.) so that the resulting language is also regular?
The answer is yes. How can you modify the DFA for to construct a DFA for ?
Yes. If is regular, then there is a DFA solving . The complement of is solved by the DFA . Take a moment to observe that this exercise allows us to say that a language is regular if and only if its complement is regular. Equivalently, a language is not regular if and only if its complement is not regular.
The answer is no. Try to think of a counter example.
No. For example, is a regular language (construct a single state DFA in which the state is accepting). On the other hand, by Theorem ( is not regular), is not regular.
Let be some finite alphabet. If and are regular languages, then the language is also regular.
Given regular languages and , we want to show that is regular. Since and are regular languages, by definition, there are DFAs and that solve and respectively (i.e. and ). To show is regular, we’ll construct a DFA that solves . The definition of will make use of and .
The idea behind the construction of is as follows. To figure out if a string is in , we can run and to see if at least one of them accepts. However, that would require scanning twice, which is something a DFA cannot do. Therefore, the main trick is to simulate both and simultaneously. For this, we can imagine having one thread for and another thread for that we run together. We can write the computation paths corresponding to the threads as follows.
| thread 1: | ||||||
| thread 2: |
Here, thread 1 represents a computation path for and thread 2 represents a computation path for . We want the above to represent the computation path of a single DFA (and we want to know if one of the threads is an accepting computation path). We can accomplish this by viewing the combination of states as a single state of . And when we read a symbol , we update according to the transition function of , and we update according to the transition function of . In more detail:
The set of states is . (Note that in the definition of a DFA, we can use any fixed finite set as the set of states. It does not matter if a state is represented as a tuple or some other object; you could rename them to be of the form if you wanted.)
The transition function is defined such that for all and for all , (Note that for , .)
The initial state is .
The set of accepting states is .
This completes the definition of . It remains to show that indeed solves the language , i.e. . We will first argue that and then argue that . Both inclusions will follow easily from the definition of and the definition of a DFA accepting a string.
: Suppose , which means either belongs to or it belongs to . Our goal is to show that . Without loss of generality, assume belongs to , or in other words, accepts (the argument is essentially identical when belongs to ). So we know that . By the definition of , . And since , (by the definition of ). So is accepted by as desired.
: Suppose that . Our goal is to show that or . Since is accepted by , we know that . By the definition of , this means that either or , i.e., is accepted by or . This implies that either or , as desired.
Let be some finite alphabet. If and are regular languages, then the language is also regular.
We want to show that regular languages are closed under the intersection operation. We know that regular languages are closed under union and closed under complementation. The result then follows since .
Give a direct proof (without using the fact that regular languages are closed under complementation, union and intersection) that if and are regular languages, then is also regular.
The proof is very similar to the proof of Theorem (Regular languages are closed under union). The only difference is the definition of , which now needs to be defined as The argument that needs to be slightly adjusted in order to agree with .
The first one is “yes” (think induction) and the second one is “no” (give a counter-example).
In part 1, we are asking whether a finite union of regular languages is regular. The answer is yes, and this can be proved using induction, where the base case corresponds to a single regular language, and the induction step corresponds to Theorem (Regular languages are closed under union). In part 2, we are asking whether a countably infinite union of regular languages is regular. The answer is no. First note that any language of cardinality 1 is regular, i.e., for any is a regular language. In particular, for any , the language of cardinality 1 is regular. But is not regular.
No. Come up with a counter-example. You can try to find one such that is .
The answer is no. Consider , which is a non-regular language. Furthermore, the complement of , which is , is non-regular. This is because regular languages are closed under complementation (Exercise (Are regular languages closed under complementation?)), so if was regular, then would also have to be regular. The union of and is , which is a regular language.
Suppose is a regular language. Show that the following languages are also regular:
Let be a DFA solving . We define to be the set of states that are “reachable” starting from the initial state . More precisely, Define a DFA for each as follows: , so the only difference between and is the starting/initial state. We claim that We now prove this equality by a double containment argument.
First, if then you know that there is some such that . So accepts. Note that this , when fed into , ends up in some state. Let’s call that state . Then accepts , i.e. . And therefore .
On the other hand suppose . Then there is some state such that . By the definition of , there is some string such that ends up in state . Since is accepted by , we have that is accepted by , i.e. . By the definition of , this implies . This concludes the proof of the claim.
Since is regular for all and is a finite set, using Exercise (Finite vs infinite union) part 1, we can conclude that is regular.
For the second part, define the set Now we can define the DFA . Observe that this DFA solves , which shows that is regular.
If are regular languages, then the language is also regular.
Given regular languages and , we want to show that is regular. Since and are regular languages, by definition, there are DFAs and that solves and respectively. To show is regular, we’ll construct a DFA that solves . The definition of will make use of and .
Before we formally define , we will introduce a few key concepts and explain the intuition behind the construction.
We know that if and only if there is a way to write as where and . With this in mind, we make the following definition. Given a word , a concatenation thread with respect to is a sequence of states where is an accepting computation path of with respect to , and is a computation path (not necessarily accepting) of with respect to . A concatenation thread like this corresponds to simulating on (at which point we require that an accepting state of is reached), and then simulating on . So a concatenation thread is really a concatenation of a thread in with a thread in .
For each way of writing as where , there is a corresponding concatenation thread for it. Note that if and only if there is a concatenation thread in which . Our goal is to construct the DFA such that it keeps track of all possible concatenation threads, and if one of the threads ends with a state in , then accepts.
At first, it might seem like one cannot keep track of all possible concatenation threads using only constant number of states. However, this is not the case. Let’s identify a concatenation thread with its sequence of ’s (i.e. the sequence of states from corresponding to the simulation of ). Consider two concatenation threads (for the sake of example, let’s take ): If, say, for some , then for all (in particular, . At the end, all we care about is whether or is an accepting state of . So at index , we do not need to remember that there are two copies of ; it suffices to keep track of one copy. In general, at any index , when we look at all the possible concatenation threads, we want to keep track of the unique states that appear at that index, and not worry about duplicates. Since we do not need to keep track of duplicated states, what we need to remember is a subset of (recall that a set cannot have duplicated elements).
The construction of we present below keeps track of all the concatenation threads using a constant number of states. The strategy is to keep a single thread for the machine , and then separate threads for machine that will correspond to the portions of the different concatenation threads. So the set of states is where the first component keeps track of the state we are at in , and the second component keeps track of all the unique states of that we can be at if we are following one of the possible concatenation threads.
Before we present the formal definition of , we introduce one more definition. Recall that the transition function of is . Using we define a new function as follows. For and , is defined to be the set of all possible states that we can end up at if we start in a state in and read the symbol . In other words, It is appropriate to view as an extension/generalization of .
Here is the formal definition of :
The set of states is .
(The first coordinate keeps track of which state we are at in the first machine , and the second coordinate keeps track of the set of states we can be at in the second machine if we follow one of the possible concatenation threads.)
The transition function is defined such that for and ,
(The first coordinate is updated according to the transition rule of the first machine. The second coordinate is updated according to the transition rule of the second machine. Since for the second machine, we are keeping track of all possible states we could be at, the generalized transition function gives us all possible states we can go to when reading a character . Note that if after applying to the first coordinate, we get a state that is an accepting state of the first machine, a new thread in must be created, which corresponds to a new concatenation thread that we need to keep track of. This is accomplished by adding to the second coordinate.)
The initial state is
(Initially, if , then there are no concatenation threads to keep track of, so the second coordinate is the empty set. On the other hand, if , then there is already a concatenation thread that we need to keep track of – the one corresponding to running the whole input word on the second machine – so we add to the second coordinate to keep track of this thread.)
The set of accepting states is .
(In other words, accepts if and only if there is a state in the second coordinate that is an accepting state of the second machine . So accepts if and only if one of the possible concatenation threads ends in an accepting state of .)
This completes the definition of . To see that indeed solves the language , i.e. , note that by construction, with input , does indeed keep track of all the possible concatenation threads. And it accepts if and only if one of those concatenation threads ends in an accepting state of . The result follows since if and only if there is a concatenation thread with respect to that ends in an accepting state of .
We defined a generalized transition function in the proof of the above theorem. This is a useful definition and we will be using it multiple times in what comes next. Therefore we repeat the definition below.
Let be a DFA. We define the generalized transition function as follows. For and ,
In the proof of Theorem (Regular languages are closed under concatenation), we defined the set of states for the DFA solving as . Construct a DFA for in which is equal to , i.e., specify how , and should be defined with respect to . Proof of correctness is not required.
As before, we have DFAs and solving and respectively. The construction for is as follows. We are given that the set of states is To define the transition function, let and . Write as , where and . Then, The initial state is And the set of accepting states is Note that this construction is not really much different from the construction given in the proof of Theorem (Regular languages are closed under concatenation) because the way the initial state and the transition function is defined, a state will always have a single element from . So one can view as an element of .
Critique the following argument that claims to establish that regular languages are closed under the star operation, that is, if is a regular language, then so is .
Let be a regular language. We know that by definition , where We know that for all , must be regular using Theorem (Regular languages are closed under concatenation). And since is regular for all , we know must be regular using Theorem (Regular languages are closed under union).
It is true that using induction, we can show that is regular for all . However, from there, we cannot conclude that is regular. Even though regular languages are closed under finite unions, they are not closed under infinite unions. See Exercise (Finite vs infinite union).
Show that regular languages are closed under the star operation as follows: First show that if is regular, then so is , which is defined as the union For this part, given a DFA for , show how to construct a DFA for . A proof of correctness is not required. In order to conclude that is regular, observe that , and use the fact that regular languages are closed under union.
We construct a DFA solving using a DFA that solves . The construction is as follows. So the elements of are subsets of . To define the transition function, for any and any , let The initial state is . And the set of accepting states is
To be added.
What are the components of a DFA?
Let be a DFA. What does denote?
Draw a DFA solving . Draw a DFA solving .
True or false: Given a language , there is at most one DFA that solves it.
Fix some alphabet . How many DFAs are there with exactly one state?
True or false: For any DFA, all the states are “reachable”. That is, if is a DFA and is one of its states, then there is a string such that .
What is the set of all possible inputs for a DFA ?
Consider the set of all DFAs with states over the alphabet such that all states are reachable from . What is the cardinality of this set?
What is the definition of a regular language?
Describe the general strategy (the high level steps) for showing that a language is not regular.
Give examples of non-regular languages.
Let be a language consisting of all strings of ’s of odd length except length . Is regular?
Let be the set of all strings in that contain at least ’s and at most ’s. Is regular?
Suppose you are given a regular language and you are asked to prove that any DFA solving must contain at least states (for some value given to you). What is a general proof strategy for establishing such a claim?
Let be a DFA solving a language and let be a DFA solving a language . Describe the components of a DFA solving .
True or false: Let denote the set of all words in either or , but not both. If and are regular, then so is .
True or false: For languages and , if and is non-regular, then is non-regular.
True or false: If is non-regular, then is non-regular.
True or false: If are non-regular languages, then so is .
True or false: Let be a non-regular language. There exists , , such that is also non-regular.
By definition a DFA has finitely many states. What is the motivation/reason for this restriction?
Consider the following decision problem: Given as input a DFA, output True if and only if there exists some string that the DFA accepts. Write the language corresponding to this decision problem using mathematical notation, and in particular, using set builder notation.
Here are the important things to keep in mind from this chapter.
Given a DFA, describe in English the language that it solves.
Given the description of a regular language, come up with a DFA that solves it.
Given a non-regular language, prove that it is indeed non-regular. Make sure you are not just memorizing a template for these types of proofs, but that you understand all the details of the strategy being employed. Apply the Feynman technique and see if you can teach this kind of proof to someone else.
In proofs establishing a closure property of regular languages, you start with one or more DFAs, and you construct a new one from them. In order to build the new DFA successfully, you have to be comfortable with the 5-tuple notation of a DFA. The constructions can get notation-heavy (with power sets and Cartesian products), but getting comfortable with mathematical notation is one of our learning objectives.
With respect to closure properties of regular languages, prioritize having a very solid understanding of closure under the union operation before you move to the more complicated constructions for the concatenation operation and star operation.